/*************************************************************************
	> File Name: 001.binheap.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 二  3/16 18:10:10 2021
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define Error(str) FatalError(str)
#define FatalError(str) fprintf(stderr, "%s\n", str), exit(1)

#define MinPQSize (10)
#define MinData (-32767)

typedef int ElementType;

typedef struct HeapStruct {
    int capacity;
    int size;
    ElementType *elements;
} *PriorityQueue;

PriorityQueue initialize(int maxElements);
void destory(PriorityQueue H);
void makeEmpty(PriorityQueue H);
void insert(ElementType x, PriorityQueue H);
ElementType deleteMin(PriorityQueue H);
ElementType findMin(PriorityQueue H);
int isEmpty(PriorityQueue H);
int isFull(PriorityQueue H);

PriorityQueue initialize(int maxElements) {
    PriorityQueue H;
    if (maxElements < MinPQSize) 
        Error("PriorityQueue is too small");

    H = malloc(sizeof(struct HeapStruct));
    if (H == NULL) 
        FatalError("Out of space!!!");
    
    /*Allocate the array plus one extra for sentinel*/
    H->elements = malloc((maxElements + 1 ) * sizeof(ElementType));
    if (H->elements == NULL) 
        FatalError("Out of space!!!");

    H->capacity = maxElements;
    H->size = 0;
    H->elements[0] = MinData;

    return H;
}

void makeEmpty(PriorityQueue H) {
    H->size = 0;
}

/* H->Element[ 0 ] is a sentinel */
void insert(ElementType x, PriorityQueue H) {
    if (isFull(H)) {
        Error("Priority queue is full");
        return ;
    }

    int i;
    for (i = ++H->size; H->elements[i / 2] > x; i /= 2) 
        H->elements[i] = H->elements[i / 2];
    H->elements[i] = x;
}

ElementType deleteMin(PriorityQueue H) {
    if (isEmpty(H)) {
        Error("Priority queue is empty");
        return H->elements[0];
    }

    ElementType minElement = H->elements[1];
    ElementType lastElement = H->elements[H->size--];

    int i, child;
    for (i = 1; i * 2 <= H->size; i = child) {
        /*Find smaller child*/
        child = 2 * i;
        if (child != H->size && H->elements[child + 1] < H->elements[child])
            child++;
        /*percolate one level*/
        if (lastElement > H->elements[child]) 
            H->elements[i] = H->elements[child];
        else 
            break;
    }
    H->elements[i] = lastElement;
    return minElement;
}

ElementType findMin(PriorityQueue H) {
    if (!isEmpty(H)) return H->elements[1];
    Error("Priority queue is empty");
    return H->elements[0];
}

int isEmpty(PriorityQueue H) {
    return H->size == 0;
}

int isFull(PriorityQueue H) {
    return H->size == H->capacity;
}

void destroy(PriorityQueue H) {
    free(H->elements);
    free(H);
}

int main() {
    srand(time(0));
    #define max_op 10
    PriorityQueue h = initialize(max_op);

    for (int i = 0; i < max_op; i++) {
        int val = rand() % 100;
        insert(val, h);
    }

    for (int i = 0; i < max_op; i++) {
        printf("%d ", deleteMin(h));
    }
    printf("\n");
    destroy(h);
    #undef max_op

    return 0;
}
